import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;

/**
 * Created by L.jp
 * Description:一个长度为n-1的递增排序数组中的所有数字都是唯一的，
 * 并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，
 * 请找出这个数字。
 *

 * User: 86189
 * Date: 2022-11-15
 * Time: 13:28
 */
public class Solution {
    //异或运算，利用0异或任何数都为任何数的原理，找出缺失的数
    /*public static int missingNumber(int[] nums) {
        //排除缺失0的情况，比如：[1]
        if(nums[0]==1){
            return 0;
        }
        for(int i = 0; i < nums.length; i++){
            //正常情况是用0异或nums[i]得到的就是i,如果不相等那么就是缺失了i
            if((0^nums[i])!=i){
                return i;
            }
        }
        //排除缺失最后一向的情况：比如[0]
        return nums.length;
    }*/
    
    
    //二分查找，二分就是利用mid的值进行考虑，在这里如果mid的值等于mid下标，那么说明mid以及mid前面没有确实元素
    //当第一次遇到mid的值与mid下标不等的时候，前面都是相等了，都比mid值大，不相等的话就是比当前mid的值小
    //缺失的元素就是在mid的左边，缺失的是下标，只返回下标即可
    public static int missingNumber(int[] nums) {
       int left=0;
       int right=nums.length-1;
       while ( left <= right ){
           int mid=left+(right-left)/2;
           //因为是递增的数，那么nums的元素应该和下标的值一样，如果中间元素的下标的值都一样，说明缺的元素在右边
           if(nums[mid]==mid){
               left=mid+1;
           }else {
               //如果中间元素和中间下标不相等，那么缺失的元素在左边
               right=mid-1;
           }
       }
       return left;
       
    }
    
    public static void main (String[] args) {
        int[] nums={0,1,2,3,4,5,6,7,9};
        System.out.println( missingNumber( nums ) );
    }
}
